package algorithm.middle;

import pojo.ListNode;

import java.util.HashMap;


/**
 * @author 江岸
 * @version V1.0
 * @ClassName: DeleteDuplicates82 82. 删除排序链表中的重复元素 II
 * @description: 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
 *
 * 返回同样按升序排列的结果链表。
 *输入：head = [1,2,3,3,4,4,5]
 * 输出：[1,2,5]
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/3/2511:30
 * @since V1.0
 */
public class DeleteDuplicates82 {

    //递归 链表
    /**
     * 1.3 递归调用
     *
     * 什么时候需要递归呢？我们想一下这两种情况：
     *
     *     如果 head.val != head.next.val ，说明头节点的值不等于下一个节点的值，所以当前的 head 节点必须保留；但是 head.next 节点要不要保留呢？我们还不知道，需要对 head.next 进行递归，即对 head.next 作为头节点的链表，去除值重复的节点。所以 head.next = self.deleteDuplicates(head.next).
     *     如果 head.val == head.next.val ，说明头节点的值等于下一个节点的值，所以当前的 head 节点必须删除；但是 head.next 节点要不要删除呢？我们还不知道，需要一直向后遍历寻找到与 head.val 不等的节点。与 head.val 相等的这一段链表都要删除，因此返回 deleteDuplicates(move);
     *
     * 作者：fuxuemingzhu
     * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/solution/fu-xue-ming-zhu-di-gui-die-dai-yi-pian-t-wy0h/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head==null || head.next==null){
            return head;
        }
        if (head.val!=head.next.val){
            head.next = deleteDuplicates(head.next);
        }else {
            ListNode move = head.next;
            while (move!=null && head.val == move.val){
                move=move.next;
            }
            return deleteDuplicates(move);
        }
        return head;
    }

    //两次遍历 计数
    public ListNode deleteDuplicates2(ListNode head) {
        if (head==null || head.next==null){
            return head;
        }
        ListNode node = head;
        HashMap<Integer, Integer> map = new HashMap<>();
        while (node!=null){
            map.put(node.val,map.getOrDefault(node.val,0)+1);
            node = node.next;
        }
        ListNode temp = new ListNode();
        temp.next = head;
        ListNode res = temp;
        while (temp.next!=null){
            if (map.get(temp.next.val)>1){
                temp.next = temp.next.next;
            }else {
                temp = temp.next;
            }
        }
        return res.next;
    }

    //83. 删除排序链表中的重复元素
    public ListNode deleteDuplicates3(ListNode head) {
        if(head==null) return null;
        ListNode temp = head;
        while(temp.next!=null){
            if(temp.val==temp.next.val){
                temp.next = temp.next.next;
            }else {
                temp = temp.next;
            }
        }
        return head;
    }
}
